// key-value 模型

public class HashBucket {

    private static class Node {

        private int key;

        private int value;

        Node next;

 

 

        public Node(int key, int value) {

            this.key = key;

            this.value = value;

        }

    }

 

 

    private Node[]  array;

    private int size;   // 当前的数据个数

    private static final double LOAD_FACTOR = 0.75;

    private static final int DEFAULT_SIZE = 8;//默认桶的大小

 

    public void put(int key, int value) {
        Node node = new Node(key, value);
        //获取key在对应数组中的位置
        //确认下标位置
        int index = key % array.length;

        Node cur = array[index];
        while (cur != null) {
            //当找到相同的数据时,需要覆盖其val
            if (cur.key == key) {
                cur.value = value;
                return;
            }
            cur = cur.next;
        }
        //没有找到相同的key,需要头插
        node.next = array[index];
        array[index] = node;
        size++;
        //检查负载因子
        if (loadFactor() >= loadFactor()) {
            //进行 扩容
            grow();
        }

    }

    //扩容
    private void grow(){
        Node[] newArray = new Node[2* array.length];
        /**
         * 1.遍历
         * 2.重写哈希
         */
        for (int i = 0; i < array.length;i++) {
            Node cur = array[i];
            while (cur != null){
                Node curNext = cur.next;
                int index = cur.key%newArray.length;
                cur.next = newArray[index];
                newArray[index] = cur;
                cur = curNext;
            }
        }

        this.array = newArray;
    }


    //作用是对哈希表进行初始化
    private void resize() {

    }
    private double loadFactor() {
        return size * 1.0 / array.length;

    }


    public HashBucket() {

    }

 

 

    public int get(int key) {
        int index = key % array.length;
        Node cur = array[index];
        while (cur != null) {
            if(cur.key == key) {
                return cur.value;
            }
            cur = cur.next;
        }
        return -1;
    }

}